package com.dycong.common.leetcode.any;

/**
 * 作用描述: 你是山西的一个煤老板，你在矿区开采了有3000吨煤需要运送到市场上去卖，从你的矿区到市场有1000公里，你手里有一列烧煤的火车，这个火车最多只能装1000吨煤，且其能耗比较大——每一公里需要耗一吨煤。请问，作为一个懂编程的煤老板的你，你会怎么运送才能运最多的煤到集市？
 * <p>
 * 由于火车一次最多只能运1000吨煤，而且每运一公里火车要消耗掉一吨煤，如果第一次运1000吨煤，运了1000公里，到了终点，火车的煤也消耗完了，显然这样是不行的，所以运到某一个位置要把煤卸载下来，然后回去再运剩下的，另外还要注意的是火车回去也要消耗煤的，这是一个反复的过程，关键是确定这个位置，另外还有一个最优的问题，也就是说火车每次运的时候都尽可能的运最多的煤。
 * <p>
 * 假设火车第一次运1000吨煤，走了500公里，消耗了500吨，还剩下500吨煤，如果卸载一些煤下来，火车就回不去了，如果不卸载，刚好能回到出发点，因为回去毕竟也要消耗掉500吨煤，这样根本就运不到煤，所以火车第一次卸载的煤的地点距离出发点一定要少于500公里。
 * <p>
 * 如果火车第一次运1000吨煤，走了250公里，卸载了500吨煤，这样刚好能回去运剩下的，同样第二次也卸载了500吨，由于第三次不用回去了，所以运到250公里的时候火车上还有1000-250=750吨煤，加上前两次卸载的煤
 * <p>
 * 那么第一次卸载煤的地点如何确定呢，考虑到最优化策略，假设距离出发点X公里的地点开始卸载煤，那么一次卸载煤为 1000-2X，同理第二次卸载煤也为1000-2X，那么第三次运到X公里处火车上煤为1000-X,那么到此所有剩下的煤为1000-2X+1000-2X+1000-X=3000-5X,考虑到最优化策略，3000-5X应该是1000的整数倍，这样才能达到火车每次都运做多的煤，
 * <p>
 * 显然应是2倍，即3000-5X=2000 ,所以X=200公里，这是剩下的煤为2000吨。那么剩下的就是把这2000吨煤再运800公里就到了目的地。同理假设再运1000吨煤到Y公里处开始卸载煤，那么有1000-2Y+1000-Y=1000,那么Y =1000/3公里，剩下煤1000吨，剩下的距离为1000-200-1000/3=466.66...公里，那么最终到目的地剩下的煤为1000-466.666=533.33吨。
 * <p>
 * 因此步骤应该是：
 * 首先运到200米处，剩2000吨煤
 * 再次运到1000/3米处，剩1000吨煤
 * 最后运到目的地，剩533.333吨煤
 * <p>
 * 对于这一类问题，如果是4000吨煤呢？如何
 * 第一次卸载煤X公里，则 1000-2X+1000-2X+1000-2X+1000-X=4000-7X=3000(为什么是3000呢，根据最优化策略，应该是1000的整数倍，最大取3000)，那么X=1000/7公里，也就是剩下3000吨煤。
 * 第二次卸载煤再往前走Y公里，则1000-2Y+1000-2Y+1000-Y=2000 ,则Y=200公里，剩下2000吨煤，
 * 第三次卸载煤再往前走Z公里，则1000-2Z+1000-Z=1000,则Z=1000/3公里，剩下1000吨煤，那么剩下的路程呢，为1000-1000/7-200-1000/3公里，
 * 那么到目的地剩下的煤为1000-(1000-1000/7-200-1000/3)=676.19吨
 *
 * @author dycong
 * @date 2019/12/24 13:18
 */
public class TransportCoal {

    public static void main(String[] args) {
        TransportCoal transportCoal = new TransportCoal();
        System.out.println(transportCoal.transportCoal(1000, 1000, 5000));
    }

    public double transportCoal(double distance, int capacity, int coal) {
        int times = (coal + capacity - 1) / capacity;
        if (times <= 1) {
            return coal - distance;
        }
        //x 个数
        int nx = 1 + 2 * (times - 1);
        double x = (coal - capacity * (times - 1)) * 1D / nx;
        coal = capacity * (times - 1);
        return transportCoal(distance - x, capacity, coal);
    }
}
